#include "definition.h"

// 自顶向下
class Solution {
 public:
  bool isBalanced(TreeNode* root) {
    if (!root) return true;
    if (abs(GetDepth(root->left) - GetDepth(root->right)) > 1) return false;
    return isBalanced(root->left) && isBalanced(root->right);
  }
  int GetDepth(TreeNode* root) {
    if (!root) return 0;
    return max(GetDepth(root->left), GetDepth(root->right)) + 1;
  }
};

// 自底向上
class Solution {
 public:
  bool isBalanced(TreeNode* root) { return recur(root) != -1; }
  // 返回左(右)子树的深度,如果其深度为-1(默认不平衡),则全树不平衡
  int recur(TreeNode* root) {
    if (!root) return 0;
    int left = recur(root->left);
    if (left == -1) return -1;
    int right = recur(root->right);
    if (right == -1) return -1;

    return abs(left - right) < 2 ? max(left, right) + 1 : -1;
  }
};